//
// Created by spiro on 19-4-8.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "sort.h"
#include "test_prepare.h"

// #define PRINT_ARRAY

/**
 * print array
 * @param arr
 * @param len
 */
void print_arr(int * arr, int len);

/**
 * test sort algorithm
 * @param arr       target sort array
 * @param len       array length
 * @param sort_name sort algorithm name
 * @param fun       sort function pointer
 */
void test_sort(const int * arr, int len, const char * sort_name, void (*sortfun) (int *, int));

void test_all_sort(const int * arr, int len);

struct sort_fun {
    char * name;
    void (*fun)(int *, int);
};

static struct sort_fun sort_fun_list[] = {
        {"bubble",              bubble_sort},
        {"insertion",           insertion_sort},
        {"merge",               merge_sort},
        {"heap",                heap_sort},
        {"quick",               quick_sort},
        {"randomized_quick",    randomized_quick_sort}
};

int main(int argc, char **argv) {

    if (argc < 2) {
        printf("Usage: %s <array length>\n", argv[0]);
        printf("Array length must greater than zero.\n");
        exit(-1);
    }

    int len = atoi(argv[1]);
    if (len == 0) {
        printf("Usage: %s <array length>\n", argv[0]);
        printf("Array length must be number and greater than zero.\n");
        exit(-2);
    }

    int a[len];

    // rand ordered
    printf("---------------------- rand-ordered\n");
    gen_rand_arr(a, len);
    test_all_sort(a, len);

    // ordered
    printf("---------------------- ordered\n");
    gen_ordered_arr(a, len);
    test_all_sort(a, len);

    // nearly ordered
    printf("---------------------- nearly ordered\n");
    gen_nearly_ordered_arr(a, len, len * 0.1);
    test_all_sort(a, len);

    // reverse ordered
    printf("---------------------- reverse ordered\n");
    gen_reverse_arr(a, len);
    test_all_sort(a, len);

    return 0;
}

void print_arr(int * arr, int len) {
    for (int i = 0; i < len; ++i) {
        if (i != 0) {
            putchar(',');
        }
        printf(" %d", arr[i]);
    }
    putchar('\n');
}

void test_sort(const int * arr, int len, const char * sort_name, void (*sortfun) (int *, int)) {
    size_t s = len * sizeof(int);
    int * t_arr = (int *) malloc(s);
    memcpy(t_arr, arr, s);

    struct timeval start, end;

    printf(">>>>> %s:\n", sort_name);

#ifdef PRINT_ARRAY
    printf("B: ");
    print_arr(t_arr, len);
#endif

    gettimeofday(&start, NULL);
    (*sortfun)(t_arr, len);
    gettimeofday(&end, NULL);

#ifdef PRINT_ARRAY
    printf("A: ");
    print_arr(t_arr, len);
#endif

    if (!is_sorted(t_arr, len)) {
        printf("****Sort failed******\n");
        free(t_arr);
        return;
    }

    free(t_arr);

    long time_take = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
    printf("take %ld us\n", time_take);
}

void test_all_sort(const int * arr, int len) {

    int sort_num = sizeof(sort_fun_list) / sizeof(struct sort_fun);
    for (int i = 0; i < sort_num; ++i) {
        test_sort(arr, len, sort_fun_list[i].name, sort_fun_list[i].fun);
    }
}